Systems can have many and/or different states, objects, events, dependencies, and interactions {complexity, system}. Complex systems share information among objects [Goodwin, 1994] [Kauffman, 1993] [May, 1976] [Pagels, 1988] [Prigogine and Nicolis, 1989] [Prigogine and Stengers, 1984] [Prigogine, 1980] [Smale, 1967].
hierarchy
Having more parts and relations allows part and relation levels.
emergence
Having more parts and relations allows new part and relation combinations.
laws
The many and varied complex-system relations make conservation laws, constancies, covarying elements, and other regularities.
flows and circuits
The many complex-system relations propagate changes throughout system.
states
Systems can return to initial or previous state or reach terminal state, so system halts or repeats. Terminal states are typically undesirable, unstable, or otherwise break system, so system must protect against them. Physical complex systems can self-destruct. They must have mechanisms to prevent halting, repeating, and breakdown or extricate themselves from such situations. Complex systems typically are stable for only some states. Stable complex systems have resting or default states.
non-isolation
Complex systems can have complex input and output.
non-isolation: energy
Stable physical complex systems require energy sources and regulate energy input and output between system and environment.
non-isolation: environment
Physical complex systems can work in only one environment type.
Regularity enumeration can measure complexity {complexity theory}| [Kauffman, 1993].
Algorithm classes require time ranges {computational complexity theory}.
System complexity measures {algorithmic information content} {algorithmic complexity, system} {Kolmogorov complexity, system} can be numbers of bits for smallest program that can run on universal Turing machines and produce same output.
algorithm
Programs produce output from input and algorithm. Theory predicts facts from data and formulas. Algorithms and formulas are similar.
number
Random numbers have programs about as long as themselves. Information has no redundancy and cannot compress {irreducible information}.
proof
Infinitely many mathematical results require algorithms or proofs as large as output and so have no useful proofs. For example, axioms have no proof. Therefore, the principle of sufficient reason is not always true.
In general, whether programs will stop, or not, is impossible to predict {halting problem}|, as shown by Turing.
Turing machine
Turing machines must have at least one rule that leads to STOP, must not move to non-existent state, must use and make only coded sequences of marked and blank squares, and must have at least one marked square on output side. Turing machines have input and rules. Number of Turing machines and number of inputs are both infinite.
Many Turing machines never reach STOP.
If people can prove that Turing machine with some input reaches or does not reach STOP, people can make complex Turing machines that include that Turing machine and answer the question whether Turing machine stops. People can program complex Turing machines to make same mark, as long as that Turing machine does not stop. Complex Turing machine can include all Turing machines, so then all Turing machines can mark definite answers for inputs, whether they stop or not. Therefore, one algorithm decides same Turing machine reaches STOP, and one algorithm decides same Turing machine does not reach STOP. However, only one algorithm is true, and the other is false. Therefore, it is impossible to prove that Turing machines will reach STOP.
halting problem
Possible Turing machines have representations as natural numbers. Possible inputs have representations as natural numbers. If numbers of inputs and machines are equal, a square natural-number array can represent all possible Turing machines and inputs. See Figure 1.
Look at sequence, to take diagonal slash, on square-array main diagonal. See Figure 2.
Change marks for numbers in diagonal sequence. See Figure 3.
This sequence is not the same as any row or column sequence, because it differs from first row and column at first number, differs from second row and column at second number, and so on. If halting problem is solvable, this sequence can represent possible Turing machine/input combination, because first part can be legitimate Turing machine and second part can be legitimate input. However, array must contain all possible sequences, because array has all possible Turing machines and all possible inputs. Contradiction makes halting problem not solvable in general.
omega
Programs have halting probabilities {omega, number} {Chaitin number}. Data bits can be input to program until program does not request another bit, because it has stopped. Random-bit input stop program after different numbers of input bits. Probability that program stops is 0.5 raised to number of bits. To find total halting probability, add random-input-experiment probabilities. Using more random-input experiments can approach omega.
Process or system complexity can be number {logical depth}| {depth of argument} of steps from original input to final output [Bennett, 1988] [Herken, 1988] [Norretranders, 1998] [Goodwin, 1994] [Kauffman, 1993] [Koch and Laurent, 1999] [May, 1976] [Pagels, 1988] [Prigogine and Nicolis, 1989] [Prigogine and Stengers, 1984] [Prigogine, 1980] [Smale, 1967]. Steps can be logical steps from premises to conclusions, cause-and-effect relationships, or algorithm steps.
Phase-space points {strange attractor}| can be, not equilibria or periodic loops, but infinitely long lines in confined regions. Strange attractors are stable, can have few dimensions, and are periodic but not exactly periodic.
Outline of Knowledge Database Home Page
Description of Outline of Knowledge Database
Date Modified: 2022.0225